'''
对于一个从小到大排序好的整数列表，给定一个目标值 n，找到 n 的插入位置。
         0  1  2  3  4
nums1 = [1, 3, 5, 7, 9]
                  ^
        [1, 3, 5, 6, 7, 9]
n = 6
         0  1  2
nums2 = [2, 4]
               ^
        [2, 4, 10]
n = 10
         0
nums3 = [1, 2]
        [0, 1, 2]
n = 0
         0  1
nums4 = [1, 6, 6]
n = 6
当插入一个已经存在在列表里的数字时，我们默认选择插在已存在的数字的前面。
'''
# 在 nums 里找到参数 n 的插入位置。
def search_insert(nums: list[int], n: int) -> int:
    pos = 0

    for num in nums:
        if num < n:
            pos += 1
        else: # num >= n
            break
    
    return pos

'''
HOMEWORK: 录音讲解以下调用的执行逻辑
search_insert_quick(nums = [11, 14, 16, 18, 22, 27]  n = 20)
'''
def search_insert_quick(nums: list[int], n: int) -> int:
    l = 0
    r = len(nums) - 1

    while l <= r:
        mid = (l + r) // 2

        if nums[mid] < n:
            l = mid + 1
        elif nums[mid] > n:
            r = mid - 1
        else:
            return mid

    return l



print(search_insert_quick(nums = [1, 3, 5, 7, 9], n = 6)) # 3
print(search_insert_quick(nums = [2, 4], n = 10))         # 2
print(search_insert_quick(nums = [1, 2], n = 0))          # 0
print(search_insert_quick(nums = [1, 6], n = 6))          # 1
